package com.fanwei.afgorithm.code25;

/**
 * @author fanwei
 * @version 1.0.0
 * @ClassName ReverseNodesInKGroup.java
 * @Description  25。K 个一组翻转链表
 * @address https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
 * @createTime 2021年11月02日 00:35:00
 */
public class ReverseNodesInKGroup {
    //fanwei 2021/11/2: ListNode的定义
     public class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }

    public ListNode reverseKGroup(ListNode head, int k) {
        //@Tips:head或k为1时候直接返回1
        if (head == null || k == 1){
            return head;
        }
        ListNode newNode = new ListNode(0);
        newNode.next = head;
        //K1: k组的开始标记
        ListNode start = newNode;
        //K1: k组的结束标记
        ListNode end = head;
        int count = 0;
        
        while (end != null){
            count++;
            //@Tips: 对链表以 k 为单位进行分组，记录每一组的起始和最后节点位置
            if (count % k == 0){
                //@Tips: 对每一组进行翻转，更换起始和最后的位置  
                start = reverse(start,end.next);
                end = start.next;
            }else {
                end = end.next;
            }
        }
        return newNode.next;
    }

    private ListNode reverse(ListNode start, ListNode end) {
        ListNode curr = start.next;
        ListNode prev = start;
        ListNode first = curr;
        while (curr != end){
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        start.next = prev;
        first.next = curr;
        return first;
    }
}
//https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/25.reverse-nodes-in-k-groups#kuo-zhan-1
